//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 
//
// 你应当 保留 两个分区中每个节点的初始相对位置。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,4,3,2,5,2], x = 3
//输出：[1,2,2,4,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [2,1], x = 2
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 200] 内 
// -100 <= Node.val <= 100 
// -200 <= x <= 200 
// 
//
// Related Topics 链表 双指针 👍 826 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-03-26 12:03:46
 * @description 86.分隔链表
 */
public class PartitionList{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PartitionList fun=new PartitionList();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
         /*用兩個鏈表,一個裝大的一个小的，然后最后拼接*/
    public ListNode partition(ListNode head, int x) {
		ListNode small=new ListNode(0);
		ListNode large=new ListNode(0);
        ListNode p=head;
        ListNode s=small,l=large;
        while(p!=null){
           if(p.val<x){
               small.next=p;
               small=small.next;
           }else {
               large.next=p;
               large=large.next;
           }
           p=p.next;
        }
        large.next=null;
        small.next=l.next;
        return s.next;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
